package com.itdfq.algorithm.divideAndConquer;

/**
 * @Author: QianMo
 * @Date: 2021/11/18 13:10
 * @Description: 其中的一根柱子上按照从小到大的顺序摞着 64 个黄金圆盘。梵天命令一个叫婆罗门的门徒将所有的圆盘移动到另一个柱子上，移动过程中必须遵守以下规则：
 * 每次只能移动柱子最顶端的一个圆盘；
 * 每个柱子上，小圆盘永远要位于大圆盘之上；
 */
public class Demo2 {

    public static int i = 0;

    public static void main(String[] args) {
        hanoi(5,'A','B','C');
    }

    /**
     *
     * @param num 圆盘的总个数
     * @param sou 第一个柱子 起始
     * @param tar 第二个柱子 目标
     * @param sux 第三个柱子 辅助
     */
    public static void hanoi(int num, char sou, char tar, char sux) {
        // 如果圆盘数量仅有 1 个，则直接从起始柱移动到目标柱
        if (num == 1) {
            System.out.println("第" + i + "次:从" + sou + "移动到" + tar);
            i++;
        } else {
            // 递归调用 hanoi() 函数，将 num-1 个圆盘从起始柱移动到辅助柱上
            hanoi(num - 1, sou, sux, tar);
            // 将起始柱上剩余的最后一个大圆盘移动到目标柱上
            System.out.println("第" + i + "次:从" + sou + "移动到" + tar);
            i++;
            // 递归调用 hanoi() 函数，将辅助柱上的 num-1 圆盘移动到目标柱上
            hanoi(num - 1, sux, tar, sou);
        }
    }


}
